//
// Created by 高森森 on 2022/2/15.
//

#ifndef LEETCODE_SOLUTION45_H
#define LEETCODE_SOLUTION45_H
#include<iostream>
#include<vector>
#include <queue>
using namespace std;
#include <memory.h>
class Solution45 {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        int dp[n+1];
        memset(dp,0, sizeof(dp));
        int indegree[n+1];
        memset(indegree,0, sizeof(indegree));
        vector<vector<int>>adjact(n+1);
        vector<vector<int>>revadjact(n+1);
        for(auto r:relations){
            indegree[r[1]]++;
            adjact[r[0]].push_back(r[1]);
            revadjact[r[1]].push_back(r[0]);
        }
        queue<int>que;
        for(int i=1;i<=n;i++){
            if(indegree[i]==0){
                dp[i]=time[i-1];
                que.push(i);
            }
        }
        int res=0;
//        int m=0;
        while(!que.empty()){
            int len=que.size();
            for(int i=0;i<len;i++){
                int node=que.front();
                 int m=0;
                que.pop();
                //当前节点的最短完成时间，等于其依赖的节点完成时间的最大值+自身
                for(int n:revadjact[node]){
                    m=max(m,dp[n]);
                }
                dp[node]=m+time[node-1];
                res=max(res,dp[node]);
                //让邻接表中该节点的邻居节点的入度-1
                for(int n:adjact[node]){
                    indegree[n]--;
                    if(indegree[n]==0)
                    {
                        que.push(n);
                    }
                }
            }
        }
        return res;
    }
};


#endif //LEETCODE_SOLUTION45_H
